1. Field
Example embodiments relate to a modular multiplication method and, for example, to a modular multiplication method, a modular multiplier and a cryptograph calculating system having the same for improving a multiplication method and a reduction method to increase a modular multiplication processing speed.
2. Description of the Related Art
Encryption methods may be generally divided into an encryption method using a secret key (or symmetric key) and an encryption method using a public key (or asymmetric key). An encryption method using a secret key is a technique in which two communication devices encrypt and transmit data or decrypt received data using the same secret key. Because the encryption method using a secret key requires the two communication devices to share the same secret key, a safe key transmitting/receiving channel only for the two communication devices is needed.
An encryption method using a public key is a technique in which a communication device encrypts data using a public key of a counterpart's communication device, transmits the encrypted data to the counterpart's communication device and decrypts received data using its secret key that is not opened. Accordingly, it is easy to manage a key in the encryption using a public key because each communication device manages only its own secret key.
Typical public key algorithms include the RSA (Ron Rivest, Adi Shamir, Len Adleman) algorithm, ECC (elliptic curve cryptography) algorithm and DH (Diffie-Hellman) algorithm. A public key encryption system employing the RSA algorithm is most widely used and uses the degree of difficulty of factorization. This RSA encryption system and other encryption systems may be used for electronic signing as well as encryption.
A fundamental arithmetic operation applied to encryption systems including the RSA encryption system is modular exponentiation. Modular exponentiation requires iterative modular multiplication. Modular multiplication generally uses a method of continuously adding a multiplicand based on bits of a multiplier and a method of continuously subtracting a modulus until the result of a multiplication performed on the multiplier and the multiplicand becomes smaller than the modulus for reduction.
For example, to encrypt a plain text M, an RSA encryption system calculates Me using a public key (e,m) (e is an encryption index) composed of two positive integers, divides the calculation result by n and forms a cipher text C using the remainder of the division. In the case of decryption, when the cipher text C is multiplied by d using a secret key (d,n) (d is a decryption index) and the multiplication result is divided by n, the remainder of the division becomes the plain text M. The encryption and decryption are represented as followsC=Me mod m, M=Cd mod n  [Equation 1]
Here, e denotes the encryption index, d denotes the decryption index and n represents a modulus.
As described above, most public key encryption systems are based on modular multiplication or modular exponentiation based on modular multiplication, and thus how efficiently a modular multiplication algorithm is constructed may represent an absolute index of system performance. In order to efficiently construct a modular multiplication algorithm, system performance should be higher, design complexity should be lower, and an area occupied by a circuit should be smaller. However, when one of these factors is improved, other factors may deteriorate. For example, a high-performance modular multiplier may have a large circuit area because it uses a parallel circuit configuration. Accordingly, modular multipliers may be constructed on the basis of trade-off strategy of the aforementioned factors.
In modular multiplying arithmetic, the number of multiplications determines the arithmetic speed, and thus a time required for the arithmetic increases as the number of multiplications increases. Further, the time required for the arithmetic increases according to sequential arithmetic characteristic of a reducing arithmetic. Moreover, the size of hardware for implementing a modular arithmetic device may be affected by interleaving of multiplication and reduction of modular arithmetic because an arithmetic block for multiplication must be separated from an arithmetic block for reduction in the case of a lack of interleaving of multiplication and reduction.
That is, for efficient modular multiplying arithmetic, a scheme of reducing the number of multiplications which the modular multiplier needs to operate or efficient multiplication and reduction in consideration of interleaving of multiplication and reduction is useful. In the case of the widely known Karatsuba algorithm, when multiplying arithmetic is performed on two numbers each having multiple bits, the number of multiplications is reduced to improve a modular multiplication processing speed.
However, conventional modular multipliers are constructed in such a manner that a multiplication block and a reduction block are separated from each other because of a lack of interleaving of multiplication and reduction, and thus hardware configuration is inefficient. Furthermore, in interleaving based modular multiplication arithmetic methods, sequential left-to-right or sequential right-to-left is applied to reduction so as to decrease a modular arithmetic processing speed.